Traffic shaping is important in digital networks. Traffic shaping involves buffering traffic and sending traffic based upon a desired profile. A traffic profile can include, but is not limited to the following properties: a level of priority relative to other traffic, buffer depth, latency through the buffer, jitter in sending the traffic contained in the buffer, and a rate at which the traffic should be sent. A common approach to traffic shaping involves the use of a queuing system to manage the profile. As traffic arrives, it is placed on the queue. The traffic is de-queued based upon its assigned drain rate. This is illustrated in FIG. 1. A single stream of traffic arrives at the input of a queue at a rate depicted by solid line 10. The desired output rate is depicted by the dotted line 12. It is highly desirable to smooth the input such that the output approaches the desired output rate 12.
To perform cost effective shaping of traffic, a traffic shaping device should be able to shape a large number of traffic profiles, as shown in FIG. 2. More particularly, FIG. 2 shows several input streams 10, 14, and 16 and desired outputs 12, 18, and 20 for those input streams. Supporting (and uniquely shaping) large numbers of traffic streams means supporting a large number of queues. However, traditional queuing structures do not scale well due to the exponential growth of instancing each queuing engine, and arbitration mechanisms that are needed to aggregate the resulting dequeued traffic to be sent. This implies that supporting a large number of queues using traditional queuing structures is inherently not cost effective.
Disadvantages of the prior methods include: 1) lack of scalability; 2) sheer size, and gate-count cost per queue for de-centralized shaping engines; 3) expensive caching/arbitration mechanisms; and 4) inability to shape traffic with a desirable line of granularity across a broad spectrum of desired rates. Therefore, a new type of queuing structure is needed.